# 78.子集
# 给你一个整数数组nums ，数组中的元素互不相同 。返回该数组所有可能的子集（幂集）。
# 解集不能包含重复的子集。你可以按任意顺序返回解集。
#
# 示例1：
# 输入：nums = [1, 2, 3]
# 输出：[[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]
#
# 示例2：
# 输入：nums = [0]
# 输出：[[], [0]]


class Solution:
    def subsets(self, nums: [int]):
        # 那么既然是无序，取过的元素不会重复取，写回溯算法的时候，for就要从startIndex开始，而不是从0开始！
        res = []
        path = []
        def backtracking(nums, index):
            res.append(path[:]) # 子集问题是找树的所有节点
            if index == len(nums): # 这里可以>=
                return
            for i in range(index,len(nums)): # 求取子集问题，不需要任何剪枝！因为子集就是要遍历整棵树。
                path.append(nums[i])
                backtracking(nums,i+1)
                path.pop()
        backtracking(nums,0)
        return res


if __name__ == '__main__':
    nums = [1, 2, 3]
    tmp = Solution()
    res = tmp.subsets(nums)
    print(res)


